struct ListNode
{
    int val;
    ListNode * next;
    ListNode() : val(0), next(nullptr)
    {}
    ListNode(int val) : val(val), next(nullptr)
    {}
    ListNode(int val, ListNode * next) : val(val), next(next)
    {}
};


class Solution 
{
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) 
    {
        ListNode _dummyHead(0, head);
        ListNode * slow = &_dummyHead;
        ListNode * fast = &_dummyHead;

        for(int i = 0; i < n; i++)
        {
            fast = fast->next;
        }

        while(fast->next != nullptr)
        {
            slow = slow->next;
            fast = fast->next;
        }

        if(fast->next == nullptr && n != 0)
        {
            ListNode * nodeToDelete = slow->next;
            slow->next = slow->next->next;
            delete nodeToDelete;
            nodeToDelete = nullptr;
        }
        return _dummyHead.next;
    }
};

#include <iostream>
#include <vector>
using namespace std;

// 辅助函数：根据数组创建链表
ListNode* createList(const vector<int>& nums) {
    ListNode dummy(0);
    ListNode* cur = &dummy;
    for (int num : nums) {
        cur->next = new ListNode(num);
        cur = cur->next;
    }
    return dummy.next;
}

// 辅助函数：打印链表
void printList(ListNode* head) {
    while (head) {
        cout << head->val;
        if (head->next) cout << " -> ";
        head = head->next;
    }
    cout << endl;
}

// 释放链表内存
void freeList(ListNode* head) {
    while (head) {
        ListNode* tmp = head;
        head = head->next;
        delete tmp;
    }
}

int main() {
    Solution sol;

    // 测试用例1：删除倒数第2个结点
    vector<int> nums1 = {1, 2, 3, 4, 5};
    ListNode* head1 = createList(nums1);
    cout << "原链表1: ";
    printList(head1);
    ListNode* res1 = sol.removeNthFromEnd(head1, 2);
    cout << "删除倒数第2个结点后: ";
    printList(res1);
    freeList(res1);

    // 测试用例2：只剩一个结点，删除倒数第1个
    vector<int> nums2 = {1};
    ListNode* head2 = createList(nums2);
    cout << "原链表2: ";
    printList(head2);
    ListNode* res2 = sol.removeNthFromEnd(head2, 1);
    cout << "删除倒数第1个结点后: ";
    printList(res2);
    freeList(res2);

    // 测试用例3：删除头结点（倒数第3个）
    vector<int> nums3 = {1, 2, 3};
    ListNode* head3 = createList(nums3);
    cout << "原链表3: ";
    printList(head3);
    ListNode* res3 = sol.removeNthFromEnd(head3, 3);
    cout << "删除倒数第3个结点后: ";
    printList(res3);
    freeList(res3);

    // 测试用例4：删除尾结点
    vector<int> nums4 = {1, 2, 3, 4};
    ListNode* head4 = createList(nums4);
    cout << "原链表4: ";
    printList(head4);
    ListNode* res4 = sol.removeNthFromEnd(head4, 1);
    cout << "删除倒数第1个结点后: ";
    printList(res4);
    freeList(res4);

    return 0;
}
